class Solution {
public:


    void _Convert(TreeNode* root, TreeNode*& prev)
    {

        if (root == nullptr)
            return;

        _Convert(root->left, prev);
        root->left = prev;
        if (prev)
            prev->right = root;

        prev = root;
        _Convert(root->right, prev);

    }


    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode* prev = nullptr;
        _Convert(pRootOfTree, prev);


        TreeNode* head = pRootOfTree;
        while (head && head->left)
        {
            head = head->left;
        }
        return head;
    }
};

